Analysis of Common Loops

for i in range(0, n, c):
    # some constant work

for (let i = 0; i < n; i += c) {
  // some constant work
}

• Example: for n = 10 and c = 2, it will run 5 times (0, 2, 4, 6, 8).
• Time complexity for this loop is $\Theta(\lfloor \frac{n}{c} \rfloor)$ . Ignoring constants, it’s $\Theta(n)$ .

for i in range(n, 0, c) # where c is negative value
    # some constant work

for (let i = n; i > 0; i -= c) {
  // some constant work
}

• Example: for n = 10 and c = 2, it will run 5 times (10, 8, 6, 4, 2).
• Time complexity for this loop is $\Theta(\lceil \frac{n}{c} \rceil)$ . Ignoring constants, it’s $\Theta(n)$ .

i = 1
    while i < n:
        # some constant work
        i *= c

for (let i = 1; i < n; i *= c) {
  // some constant work
}

• Example: For n = 32 and c = 2, it will be executed 5 times 1, 2, 4, 8, 16. For n = 33 and c = 2, it will be executed 6 times 1, 2, 4, 8, 16, 32. Generalizing, it runs for $1, c, c^2, c^3, ..., c^{k-1}$ i.e. it runs $k$ times from $1$ to $k-1$ .

  $$c^{k-1} < n \\ k-1 < \log_c n \\ k < \log_c n + 1$$

  So, the loop is going to run $\log_c n + 1$ times.

• Time complexity for this loop is $\Theta(\log n)$ .

• Note that base of the log doesn’t matter, since bases can be converted by simple multiplication or division operations and in asymptotic analysis constants are ignored.

i = n
    while i > 1:
        # some constant work
        i //= c # // is integer division

for (let i = n; i > 1; i /= c) {
  // some constant work
}

• Example:
  For n = 32 and c = 2, it will be executed 5 times 32, 16, 8, 4, 2. For n = 33 and c = 2, it will be executed 6 times 33, 16, 8, 4, 2`.
• Time complexity for this loop is $\Theta(\log n)$ .

i = 2
    while i < n:
        # some constant work
        i = pow(i, c)

for (let i = 2; i < n; i = Math.pow(i, c)) {
  // some constant work
}

• Example: For c = 2 and n = 32 it’s going to run for $2, 2^2, {(2^2)}^2$ i.e. 2, 4, 16.

  Let’s find out the number of times the loop runs:

  $$2, 2^c, {(2^c)}^c \\ 2, 2^c, 2^{c^2}, ...2^{c^{k-1}} \text{\footnotesize k is the number of times it runs} \\ 2^{c^{k-1}} < n \\ c^{k-1} < \log_2 n \\ k - 1 < \log_2 \log_2 n \\ k < \log_2 \log_2 n + 1$$

• Time complexity of this loop is $\Theta(\log\log n)$ .

def fun(n):
    for i in range(n):          # 𝛳(n)
        # some constant work
    i = 0
    while i < n:                # 𝛳(log n)
        # some constant work
        i *= 2
    for i in range(1, 100):     # 𝛳(1)
        # some constant work

function fun(n) {
  for (let i = 0; i < n; i++) {
    // some constant work
  }
  i = 0;
  while(i < n) {
    i *= n;
  }
  for (i = 0; i < 100; i++) {
    // some constant work
  }

}

• Since the work is sequential, we add the values $\Theta(n) + \Theta(\log n) + \Theta(1)$ .
  Ignoring lower order terms, the complexity of this function is $\Theta(n)$ .

def fun(n):
    for i in range(n):            # 𝛳(n)
        j = 0
        while j < n:              # 𝛳(log n)
            # some constant work
            j *= 2

function fun(n) {
  for(let i = 0; i < n; i++) {
    let j = 0;
    while(j < n) {
      j *= 2;
    }
  }
}

• Since it’s a nested loop,we multiply the values $\Theta(n) * \Theta(\log n)$ .
  Therefore the complexity is $\Theta(n \log n)$ .

def fun(n):
    for i in range(n):          # 𝛳(n)
        for j in range(n):      # 𝛳(n)
            # some constant work

function fun(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // some constant work
    }
  }
}

• The time complexity is $\Theta(n^2)$ .